import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

public class Leetcode310 {
//    public List<Integer> findMinHeightTrees(int n, int[][] edges) {
//        List<List<Integer>> list = new ArrayList<>(n);
//
//        for (int[] edge : edges) {
//            setListEdge(list, edge[0], edge[1]);
//            setListEdge(list, edge[1], edge[0]);
//        }
//
//
//        int maxIndex = getMaxEdgeIndex(n, list, edges[0][0]);
//
//        maxIndex = getMaxEdgeIndex(n, list, maxIndex);
//
//
//    }

    private int getMaxEdgeIndex(int n, List<List<Integer>> list, int x) {
        int maxIndex = 0;
        int maxNumber = Integer.MIN_VALUE;
        Deque<Integer> deque = new ArrayDeque<>();
        deque.add(x);

        boolean[] isHandle = new boolean[n];
        int[] res = new int[n];
        while (!deque.isEmpty()) {
            int index = deque.pop();
            isHandle[index] = true;
            List<Integer> next = list.get(index);
            for (Integer integer : next) {
                res[integer] = res[index] + 1;
                if (res[integer] > maxNumber) {
                    maxIndex = integer;
                    maxNumber = res[integer];
                }

                if (!isHandle[index]) {
                    deque.add(integer);
                }
            }
        }

        return maxIndex;
    }

    private void setListEdge(List<List<Integer>> list, int edge1, int edge2) {
        List<Integer> list1 = list.get(edge1);
        if (list1 == null) {
            list1 = new ArrayList<>();
        }
        list1.add(edge2);
        list.set(0, list1);
    }
}
